Computing Quadratic Integer Relations
Newcastle, NSW, December 7–10th 2021
For convenience, we will usually think of x∈ Rn and a∈ Zn and say that a is an integer realtion of x.
For convenience, we will usually think of x∈ Cn and a∈ Z[i]n and say that a is an integer realtion of x.
When talking about integer relations in general, we use the following notation so as to encapsulate all cases.
We will use F to denote the field of numbers which we are relating and we will use O to denote the ring of integers from which the relation elements are from.
The previous definitions we call the classical cases. That is, when O=Z, F=R, and when O=Z[i], F=C.
An information theoretic argument shows that in order to numerically compute an integer relation on n numbers, where the relation consists of integers with no more than d digits, then at least nd decimal digits of precision need to be used.
In the case of complex numbers and Gaussian integers, the number of digits is the number of digits in the real part, or the imaginary part, whichever is larger.
- LLL (indirectly)
- PSLQ (directly)
LLL
The LLL algorithm was introduced by Lenstra, Lenstra Jr, and Lovasz in 1982.
It is not an algorithm for computing integer relations directly. Instead it finds short lattice vectors
It can, however, be used to compute integer relations
LLL
Let B={b1,…,bn}⊂Fn be a linearly independent set of vectors. The set L={λ1b1,…,λnbn:λ1∈O} is the lattice spanned by B. We call B the basis of the lattice L
We will sometimes refer to an O-lattice if we need to specify the integer ring explicitly.
LLL
Given a basis B for a lattice L, the LLL algorithm computes a basis B′=(b′1,…,b′n) such that |μi,j|≤12 for 1≤j<i≤n||b∗i+μi,jb∗i−1||2≥34||b∗i−1||2 for 1<i≤n where b∗i=b′i−∑i−1j=1μi,jb∗j and μi,j=b′i⋅b∗j||b∗j||2
LLL
To find an integer relation on x=(x1,…,xn)∈Rn we can use LLL on the lattice L:=[100⋯0Nx1010⋯0Nx2⋮⋮⋱⋯⋮⋮000⋯1Nxn] for some N∈R.
Think of this as the augmented matrix [InNx].
LLL
Elements of the lattice look like (λ1,…,λn,N(λ1x1+⋯+λnxn)) So if the λi are an integer relation for x then the last term will be 0.
We can prove that if N is large enough, then the first element of the reduced lattice must contain the integer relation.
LLL
For the complex case where n z=(z1,…,zn)∈Cn we still use the augmented lattice L:=[InNz] like we did for the real case.
However we then construct a 2nd augmented lattice [ℜLℑL−ℑLℜL] and use LLL on that lattice.
As with the real case, so long as N is large enough then the procedure must find an integer relation.
LLL
In all cases, we don't know how large to make N before we start. So we must use trial and error.
We have found, experimentally, that with numeric (floating point) calculations it is possible for N to be too large, even though the theory requires N to be “sufficiently large”.
PSLQ
The PSLQ algorithm was introduced by Ferguson & Bailey in 1988. It was later analysed by Ferguson, Bailey, and Arno in 1999
It can handle both the real and complex cases directly.
We will not discuss the details of the algorithm itself. However we will establish some facts.
PSLQ
Observe that in both the real and complex cases O forms a lattice, and that O⊂F.
Let x∈F. An integer a∈O is a nearest integer if |x−a| is maximal. A function ⌈⋅⌋:F→O is a nearest integer functino if it maps each x∈F to one of its nearest integers.
We denote by ⌈⋅⌋O if we need to be specific.
PSLQ
There are parameters: γ,ρ, and τ that must satisfy 1ρ≥|x−⌈x⌋| for all x∈F1<τ≤ρ1τ2=1γ2+1ρ2
ρ is bounded by the integer lattice; choose to minimise 1/ρ.
γ is minimised when τ=1; choose any larger value.
τ is fixed by the choice of γ and the value of ρ.
PSLQ
Each iteration of the PSLQ algorithm finds an increased lower bound on the norm of any integer relation on the input.
The algorithm can terminate when that bound exceeds some threshold.
If the algorithm finds a relation, a then ||a||≤γn−2M where M is the norm of the smallest possible relation.
PSLQ
In Principle:
- We give PSLQ:
- The numbers we wish to find a relation for.
- An upper bound, b, for the Euclidean norm of the relation we wish to find.
- PSLQ gives either:
- A relation, a where ‖a‖≤b and ‖a‖≤γn−2M.
- A declaration that no such relation exists.
In Practice:
Due to floating point arithmetic and speed optimisations.
- We give PSLQ:
- The numbers we wish to find a relation for
- PSLQ gives:
- A relation accurate to the calculation precision with no bound guarantee.
Comparing LLL and PSLQ
- PSLQ is designed specifically for integer relation compuation
- In experimental testing:
- PSLQ required lower precision than LLL (for the same relation).
- PSLQ took less time than LLL (for the same relation).
Algebraic Number Theory
Let F be a field. If F is a subfield of some other field K (i.e., F⊆K then we call K a field extension (or, equivalently an extension field) of F.
We denote this by K:F when we need to be explicit about the base field and the extension.
Note that the literature often uses the notation K/F instead.
Algebraic Number Theory
Let F be a field, and consider an extension field K:F. An element k∈K is said to be algebraic over F if it satisfies fnkn+⋯+f1k+f0=0 for some n∈N and fi∈F. Note that fn≠0.
For example √2 satisfies k2−2=0 and so is algebraic over the rationals.
Algebraic Number Theory
Let D be an integral domain and consider an extension field K:F such that D⊆K. An element k∈K is said to be integeral over F if it satisfies a monic polynomial kn+dn−1kn−1+⋯+d1k+d0=0 for some n∈N and di∈D
An integral domain is a commutative ring with multiplicative identity and no non-zero elements d1,d2 with the property that d1d2=0.
Algebraic Number Theory
Let z∈C.
We denote by Q(z) the smallest subfield of C that contains both Q and z.
We denote by Z[z] the smallest subring of C that contains both Z and z.
Note that the ring Z is often called the “rational integers” to avoid ambiguity.
Algebraic Number Theory
We are primarily interested in extension fields of Q.
A number z∈C is an algebraic number (or simply algebraic) if it is algebraic over Q.
A number z∈C is an algebraic integer if it is integral over Z.
The ring of all algebraic integers is denoted by A.
An algebraic extension is real if K⊆R and complex otherwise.
Algebraic Number Theory
We are primarily interested in extension fields of Q.
An extension field K:Q is an algebraic extension field (or simply an algebraic extension if every k∈K is an algebraic number.
Its ring of integers of K, denoted OK, is K∩A. We call such rings algebraic integers
Quadratic Fields
We will restrict our attention to quadratic extension fields. These are fields of the form: Q(√D)={q1+q2√D:qi∈Q} wher D∈Z is square free.
Elements of these fields satisfy quadratic (or lower degree) polynomials with rational coefficients.
Quadratic Fields
The algebraic integers of a quadratic field (which we call quadratic integers) are of the form OQ(√D)=Z[ω]={m1+m2ω:mi∈Z} where ω={√D if D≡2,3(mod4)1+√D2 if D≡1(mod4)
D≡2,3(mod4)
D≡1(mod4)
Quadratic Fields
Finally we mention a special class of quadratic fields.
Relations With Algebraic Integers
Recall the definiton of an integer relation:
Relations With Algebraic Integers
For relations of algebraic integers we specify an intermediate extension field.
Let F∈{R,C} and let K be an algebraic extension field. Let O=OK.
Let x1,…,xn∈F. Integers, a1,…,an∈O are an algebraic integer relation (or a K-integer relation) of the original numbers xi if a1x1+⋯+anxn=0
Reduction to Classical Cases
Observe that for an quadratic integer relation: (m1,1+m1,2ω)x1+⋯+(mn,1+mn,2ω)xn=(m1,1x1+⋯+mn,1xn)+(m1,2ωx1+⋯mn,2ωxn)
This suggests a way to reduce a quadratic integer relation to a classical one.
Reduction to Classical Cases
Given (x1,…,xn)∈Fn we construct (x1,…,xn,x1ω,…,xnω)∈F2n and search for a classical integer relation on that.
We recover the integer relation by taking ak+an+kω for 1≤k≤n.
This works well for real quadratic fields (i.e., when D>1). It works less well for complex quadratic fields.
Reduction to Classical Cases
In the complex case, the integers are of the form ak=mk,1+mk,2i. So when we attempt to recover the relation we get (mk,1+mk,2i)+(mk+n,1+mk+n,2i)ω after expansion and some simplification we get α1+β2i√|D|+α2i−β2√|D| for α1,β1∈Z which is not an algebraic integer in Q(√D) if α2≠0 or β2≠0.
Reduction to Classical Cases
Much of the time the reduction technique works fine, and gives good answers even in the complex cases.
When it does not work, we try two techniques to nonetheless extract a relation.
Reduction to Classical Cases
Decomposition method
We observe that α1+β2i√|D|+α2i−β2√|D| can be written as (α1+β2i√|D|)+i(α2+β2i√|D|) and we have two possible algebraic integers embedded. We try extracting only these.
Reduction to Classical Cases
Conjugate Method
Given α1+β2i√|D|+α2i−β2√|D| a conjugate is α1−β2i√|D|−α2i−β2√|D|
Multiplying the number by its conjugate gives an element of OQ(√D). We multiply all elements of the relation by the conjugate of only one of the elements.
Reduction to Classical Cases
Both the methods for correcting the complex case work well in practice.
We do not have proofs that they will always be correct. It is nonetheless easy to just try them, and check the extracted relation.
Using LLL
To compute an algebraic integer n z=(z1,…,zn)∈Fn we still use the augmented lattice L:=[InNz] like we did for the real case.
However we then construct a 2nd augmented lattice. [ℜLℑLW1LW2L] and use LLL on that lattice.
Using LLL
However we then construct a 2nd augmented lattice. [ℜLℑLW1LW2L] and use LLL on that lattice.
W1xk={−√|D|ℑxk if if D≡2,3(mod4)(ℜxk−√|D|ℑxk)/2 if D≡1(mod4) W2xk={√|D|ℜxk if if D≡2,3(mod4)(ℑxk+√|D|ℜxk)/2 if D≡1(mod4)
Using LLL
As with the other cases, so long as N is large enough then the procedure must find an algebraic integer relation.
Modifying PSLQ
We attempt to modify PSLQ while keeping the existing theory.
We simply use a quadratic integer nearest integer function, and modify the algorithm to allow us to specify the quadratic extension field we wish to use.
Modifying PSLQ
We simply use a quadratic integer nearest integer function, and modify the algorithm to allow us to specify the quadratic extension field we wish to use.
This introduces a problem: for real quadratic extension fields, the integers do not form a lattice (there is no unique nearest integer to a field element), so we cannot use the existing theory.
We restrict our attention to the complex cases, then.
Modifying PSLQ
We restrict our attention to the complex cases, then.
In these cases we have a more subtle problem.
As D increases, the parameter ρ decreases, until eventually ρ<1 making it impossible to satisfy the 1<τ≤ρ condition.
Modifying PSLQ
In these cases we have a more subtle problem.
As D increases, the parameter ρ decreases, until eventually ρ<1 making it impossible to satisfy the 1<τ≤ρ condition.
The complex quadratic fields that do not exhibit these problems are exactly: Q(√−2),Q(√−3),Q(√−7),Q(√−11)
Modifying PSLQ
As D increases, the parameter ρ decreases, until eventually ρ<1 making it impossible to satisfy the 1<τ≤ρ condition.
The complex quadratic fields that do not exhibit these problems are exactly: Q(√−2),Q(√−3),Q(√−7),Q(√−11)
These are precisely the complex quadratic norm Euclidean fields.
Modifying PSLQ
The complex quadratic fields that do not exhibit these problems are exactly: Q(√−2),Q(√−3),Q(√−7),Q(√−11)
We note that we've had surprising success with the modified PSLQ on Q(√−5),Q(√−6),Q(√−10) even though they do not fit the existing theory.